package LC;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-22 11:09
 * 238. 除自身以外数组的乘积
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
 */

public class ProductOfArrayExceptSelf {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(nums1)));
//        int[] nums2 = {-1, 1, 0, -3, 3};
//        System.out.println(Arrays.toString(productExceptSelf(nums2)));
    }

    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < res.length; i++) {
            res[i] = 1;
        }
        int preMul = 1; // 前缀乘积
        int postMul = 1;    // 后缀乘积
        for (int i = 0; i < n; i++) {
            res[i] = res[i] * preMul;   //当前的res值等于前缀乘积
            preMul = preMul * nums[i];  // 更新前缀乘积，给下一个i使用
            res[n - 1 - i] = res[n - 1 - i] * postMul;  // 当前的res值等于后缀乘积
            postMul = postMul * nums[n - 1 - i];// 后缀乘积 // 更新后缀乘积，给下一个i使用
        }
        return res;
    }
}
